package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/6/20 9:58
 * @description：https://leetcode-cn.com/problems/n-queens-ii/
 */
public class 八皇后2 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.totalNQueens(8));
    }

    class Solution {
        int max;
        int[] arr;
        int count;

        public int totalNQueens(int n) {
            this.max = n;
            this.arr = new int[n];
            check(0);
            return count;
        }

        private void check(int n) {
            if (n == max) {
                count++;
                return;
            }
            for (int i = 0; i < max; i++) {
                arr[n] = i;
                if (judge(n)) {
                    check(n + 1);
                }
            }
        }

        private boolean judge(int n) {
            for (int i = 0; i < n; i++) {
                if (arr[i] == arr[n] || Math.abs(arr[n] - arr[i]) == Math.abs(n - i)) {
                    return false;
                }
            }
            return true;
        }
    }
}
